#include <stdio.h>
#include <stdlib.h>

typedef enum { false, true } bool;
typedef int ElemSet; /* 默认元素为整型 */
#define kMaxSize 100  /* 多路归并的最大顺串数量 */
#define EndCode 1e9   /* 当键值小为胜者时，用超大数表示文件结束 */
typedef struct LoserTreeNode *LoserTree;
struct LoserTreeNode {
    int n; /* 当前选手数 */
    int n_L; /* 最底层外部结点数 */
    int n_B; /* 最底层外部结点之上的结点总数 */
    int *B; /* 存放下标的胜者树数组 */
    ElemSet *L; /* 元素数组 */
};

int Winner(LoserTree tree, int x, int y) {
    /* 返回键值严格小的胜者 */
    return (tree->L[x] < tree->L[y]) ? x : y;
}

int Loser(LoserTree tree, int x, int y) {
    /* 返回键值大于等于的败者 */
    return (tree->L[x] >= tree->L[y]) ? x : y;
}

int FinalWinner(LoserTree tree) {
    /* 返回全局胜者 */
    return tree->B[0];
}

/* 算法13-2：从内部结点到树根的路径上进行比赛 Play(tree, p, left, right) */
void Play(LoserTree tree, int p, int left, int right) {
    int winner1, winner2;

    tree->B[p] = Loser(tree, left, right); /* 将败者索引放在B[p]中 */
    winner1 = Winner(tree, left, right); /* 将胜者索引暂存在winner1中 */
    while (p > 1
    && p % 2 == 1) { /* p是某个结点右孩子，需要沿路径继续向上比赛 */
        /* 胜者和B[p]父结点所标识的外部结点相比较 */
        winner2 = Winner(tree, winner1,
                         tree->B[p >> 1]); /* 新的胜者索引暂存在winner2中 */
        tree->B[p >> 1] = Loser(tree, winner1,
                                tree->B[p >> 1]); /* 新的败者索引存在B[p/2]中 */
        winner1 = winner2;
        p >>= 1;
    }
    /* 结束循环(即B[p]是左孩子，或者B[1])之后，在B[p]的父结点写入胜者索引 */
    tree->B[p >> 1] = winner1;
}
/* 算法13-2 结束 */

/* 算法13-1：初始化败者树 InitLoserTree(tree, array, size) */
void InitLoserTree(LoserTree tree, ElemSet array[], int size) {
    int d, logn, p, i;

    tree->n = size;
    tree->L = array; /* 外部结点数组 */
    d = 0;
    logn = tree->n - 1;
    while (logn > 0) { /* d = log_2 {tree.n-1}*/
        logn >>= 1;
        d++;
    }
    d--;
    tree->n_L = (tree->n - (1 << d)) << 1;
    tree->n_B = (1 << (d + 1)) - 1;
    tree->B = (int *)malloc(sizeof(int) * tree->n_B); /* 内部结点数组 */
    i = 2;
    while (i <= tree->n_L) {
        p = (i + tree->n_B) >> 1;
        Play(tree, p, i - 1, i); /* 最底层外部结点比赛 */
        i += 2;
    }
    /* 处理其余外部结点 */
    if (tree->n % 2 == 1) { /* n为奇数，内部结点和外部结点比赛 */
        /* 这里用L[n_L+1]和它的父结点比赛 */
        /* 因为此时它的父结点中存放的是其兄弟结点处的比赛胜者索引 */
        Play(tree, tree->n >> 1, tree->B[(tree->n - 1) >> 1], tree->n_L + 1);
        i = tree->n_L + 3;
    } else {
        i = tree->n_L + 2;
    }
    while (i <= tree->n) {
        p = (i - tree->n_L + tree->n - 1) >> 1;
        Play(tree, p, i - 1, i); /* 剩余外部结点的比赛 */
        i += 2;
    }
}
/* 算法13-1 结束 */

/* 算法13-3：重构时从外部结点到树根的路径上重新进行比赛 RePlay(tree, i) */
void RePlay(LoserTree tree, int i) {
    int winner, p;

    if (i <= tree->n_L) { /* 确定父结点的位置 */
        p = (i + tree->n_B) >> 1;
    } else {
        p = (i - tree->n_L + tree->n - 1) >> 1;
    }
    tree->B[0] = Winner(tree, i,
                        tree->B[p]); /* B[0]中始终保存胜者的索引 */
    tree->B[p] = Loser(tree, i, tree->B[p]); /* B[p]中保存败者的索引 */
    while ((p >> 1) >= 1) { /* 沿路径向上比赛 */
        winner = Winner(tree, tree->B[p >> 1],
                        tree->B[0]); /* winner临时存放胜者的索引 */
        tree->B[p >> 1] = Loser(tree, tree->B[p >> 1], tree->B[0]);
        tree->B[0] = winner;
        p >>= 1;
    }
}
/* 算法13-3 结束 */

/* 缓冲区定义及操作 */
#define kMaxBuff 10   /* 缓冲区最大容量 */
typedef int Position; /* 数组下标为数据位置 */
typedef struct BufferNode *Buffers;
struct BufferNode {
    ElemSet b[kMaxBuff]; /* 缓冲区数据数组 */
    Position front; /* 前端位置 */
    Position rear; /* 后端位置 */
    int capacity; /* 总容量 */
};

Buffers InitBuffer() {
    /* 创建一块缓冲区 */
    Buffers buff;

    buff = (Buffers)malloc(sizeof(struct BufferNode));
    buff->capacity = kMaxBuff;
    buff->front = buff->rear = 0;

    return buff;
}

void Flush(Buffers buff, FILE *f) {
    /* 将buff全部写入f */
    buff->front = 0;
    while (buff->front < buff->rear) { /* 自顶向下处理 */
        fprintf(f, "%d\n", buff->b[buff->front]);
        buff->front++;
    }
    buff->front = buff->rear = 0; /* 清空缓冲区 */
}

bool FillBuffer(Buffers buff, FILE *f) {
    /* 从f读入一块数据到buff */
    int i;

    buff->front = buff->rear = 0; /* 清空缓冲区 */
    if (fscanf(f, "%d", &buff->b[0]) == EOF) {
        return false; /* 如果一个数据都读不进，说明文件已空，返回读取失败标志 */
    } else {
        buff->rear++; /* 成功读取第一个数据 */
    }
    for (i = 1; i < buff->capacity; i++) {
        if (fscanf(f, "%d", &buff->b[i]) == EOF) {
            break; /* 一直读到文件结尾 */
        } else
            buff->rear++;
    }
    return true;
}

bool IsEmpty(Buffers buff) {
    /* 判断buff是否为空 */
    return (buff->front == buff->rear);
}

bool IsFull(Buffers buff) {
    /* 判断buff是否为满 */
    return (buff->rear == buff->capacity);
}

void Write(Buffers buff, ElemSet x) {
    /* 将数据x插入buff */
    buff->b[buff->rear] = x;
    buff->rear++;
}

ElemSet Read(Buffers buff) {
    /* 从buff中读取一个数据 */
    ElemSet ret = buff->b[buff->front];
    buff->front++;
    return ret;
}
/* 缓冲区定义及操作结束 */

/* 算法 13-4：利用败者树的多路归并排序算法 MultiMerge(tree, racer, buffer_pool, f, size) */
void MultiMerge(LoserTree tree, ElemSet racer[], Buffers buffer_pool[],
                FILE *f[], int size) {
    int winner;

    InitLoserTree(tree, racer, size); /* 初始化败者树 */
    winner = FinalWinner(tree); /* 取得最终胜者索引 */
    while (racer[winner] != EndCode) { /* 把胜者插入到输出缓冲区中 */
        if (IsFull(buffer_pool[0]) ==
                    true) { /* 输出缓冲区满，Flush到磁盘文件去 */
            Flush(buffer_pool[0], f[0]);
        }
        Write(buffer_pool[0], racer[winner]);
        /* 从输入缓冲区读入一个新的竞赛者 */
        if (IsEmpty(buffer_pool[winner]) == false) { /* 输入缓冲区不为空 */
            racer[winner] = Read(
                                buffer_pool[winner]); /* 从缓冲区读数据放进racer[winner] */
        } else {
            /* 如果对应的输入文件还有数据，从输入文件读入到输入缓冲区 */
            if (FillBuffer(buffer_pool[winner], f[winner]) == true) {
                racer[winner] = Read(
                                    buffer_pool[winner]); /* 从缓冲区读数据放进racer[winner] */
            } else { /* 对应的输入文件没有数据 */
                racer[winner] = EndCode;
            }
        }
        RePlay(tree, winner); /* 重新进行比赛，取得胜者索引 */
        winner = FinalWinner(tree);
    }
    Flush(buffer_pool[0],
          f[0]); /* 把输出缓冲区中剩余的数据写进磁盘文件 */
}
/* 算法13-4 结束 */

#define kMaxStrLen 10

int main(void) {
    FILE *f[kMaxSize +
            1]; /* f[0]为输出文件，f[1]~f[kMaxSize]为输入文件 */
    char fname[kMaxSize +
               1][kMaxStrLen]; /* 文件名，不超过(kMaxStrLen-1)个字符 */
    Buffers buffer_pool[kMaxSize + 1]; /* 对应的输出、输入缓冲区 */
    ElemSet racer[kMaxSize +
                  1]; /* 比赛者数组，即败者树外部结点数组 */
    LoserTree tree; /* 败者树 */
    int n, i, j;

    scanf("%d\n", &n);
    scanf("%s\n", fname[0]); /* 读输出文件名 */
    f[0] = fopen(fname[0], "w"); /* 打开输出文件，待写 */
    for (i = 1; i <= n; i++) {
        scanf("%s\n", fname[i]); /* 读输入文件名 */
        f[i] = fopen(fname[i], "r"); /* 打开输入文件，待读 */
    }
    tree = (LoserTree)malloc(sizeof(struct
                                    LoserTreeNode)); /* 创建败者树结点 */
    buffer_pool[0] = InitBuffer(); /* 初始化空的输出缓冲区 */
    for (i = 1; i <= n; i++) {
        fscanf(f[i], "%d",
               &racer[i]); /* 每个顺串的第一个数据进入败者树准备比赛 */
        buffer_pool[i] = InitBuffer();
        FillBuffer(buffer_pool[i],
                   f[i]); /* 从每个文件中读入一块数据到输入缓冲区 */
    }
    MultiMerge(tree, racer, buffer_pool, f,
               n); /* 归并排序，结果在输出文件里 */
    for (i = 0; i < n; i++) {
        fclose(f[i]);
    }

    return 0;
}